package two_pointer.leetcode_42;

import java.util.ArrayDeque;
import java.util.Deque;

public class StackSolution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 什么时候才可以接水？ 当前 i 柱子的高度「大于」栈顶柱子的高度
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 可以接到雨水的柱子的高度
                int h = height[stack.pop()];
                // 特殊情况考虑，[0, 1] 当遍历到 1 时，满足当前柱子高度「大于」栈顶柱子的高度，但是由于不存在左边界柱子，无法形成雨水
                if (stack.isEmpty()) {
                    break;
                }
                // 只能在柱子上方接水，所以要 「减去可以接到雨水的柱子的高度」
                // 形成的雨水量 = (Math.min(当前 i 柱子的高度, 栈顶柱子的高度) - 可以接到雨水的柱子的高度) * 两柱子的宽度
                // 计算宽度
                int distance = i - stack.peek() - 1;
                // 计算雨水量
                sum = (Math.min(height[i], height[stack.peek()]) - h) * distance + sum;
            }
            // 当前柱子可能与后续的柱子形成雨水，所以将当前柱子入栈
            stack.push(i);
        }
        return sum;
    }
}
